COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "memo.pub[let,jmc]" source
C00014 ENDMK
C⊗;
.require "memo.pub[let,jmc]" source;
.cb On sequence extrapolation as an AI problem

	This idea came up in a discussion with Gray Clossman, who
is interested in sequence extrapolation as an AI problem.

	Eliot Handleman's request for information on prediction has
inspired me to inflict the following considerations on the community.

Roofs and Boxes

	Many people have proposed sequence extrapolation as a prototype AI
problem.  The idea is that a person's life is a sequence of sensory
stimuli, and that science consists of inventing ways of predicting the
future of this sequence.  To this end many sequence extrapolating programs
have been written starting with those that predict sequences of integers
by taking differences and determining the co-efficients of a polynomial.

	It has always seemed to me that starting this way distorts the
heuristic character of both common sense and science.  Both of them think
about permanent aspects of the world and use the sequence of sense data
only to design and confirm hypotheses about these permanent aspects.  The
following sequence problem seems to me to typify the break between
hypotheses about the world and sequence extrapolation.

The ball bouncing in the rectilinear world - roofs and boxes

	Suppose there is a rectangular two dimensional room.  In this room
are a number of objects having the form of rectangles.  A ball moves in
the room with constant velocity but bounces with angle of incidence equal
to angle of reflection whenever it hits a wall or an object.  The observer
cannot see the objects or the walls.  All he sees is the x-co-ordinate of
the ball at integer times but only when the ball is visible from the front
of the room.  This provides him with a sequence of numbers which he can
try to extrapolate.  Until the ball bounces off something or goes under
something, linear extrapolation works.

	Suppose first that the observer knows that he is dealing with this
kind of ball-in-room problem and only doesn't know the locations of the
objects and the walls.  After he has observed the situation for a while he
will have partial information about the objects and their locations.  For
example, he may note that he has never been in a certain part of the room
so there may be unknown objects there.  Also he may have three sides of a
certain rectangle but may not know the fourth side, because he has never
bounced of that side yet.  He may extrapolate that he won't have the
opportunity of bouncing off that side for a long time.

	Alternatively we may suppose that the observer doesn't
initially know about balls bouncing off rectangles but only knows
the sequence and must infer this using a general sequence extrapolation
mechanism.  Our view is that this observer, whether human or machine,
can make progress only by guessing the underlying model.  At first
he may imagine a one dimensional bouncing model, but this will be
refuted the first time the ball doesn't bounce at an x-co-ordinate
where it has previously bounced.  Indeed he has to keep open
the possibility that the room is really 3  or more dimensional or that
more general objects than rectangles exist.

	We can elaborate the problem by supposing that when the ball
bounces off the front wall, the experimenter can put a paddle at an angle
and determine the angly of bounce so as to cause the ball to enter regions
where more information is wanted.

	Assuming the rectangles having edges parallel to the axes makes
the problem easier in an obvious sense but more difficult in the sense
that there is less interaction between the observable x-co-ordinate and
the unobservable y-co-ordinate.

	It would be interesting to determine the condition on the x-path
that distinguishes 2-dimensional from 3-dimensional worlds, if there is
one.  Unless we assume that the room has some limited size, there need be
no distinction.  Thus we must make the never-fully-verified assumption
that some of the repetititions in sequences of bounces are because the
ball hit the front or back wall and bounced again off the same surfaces
rather than similar surfaces further back.

	I am skeptical that an AI program fundamentally based on the idea
of sequence extrapolation is the right idea here.  Donald Michie suggests
that the "domain experts" for this kind of problem of inferring a
mechanism that produces a sequence are cryptanalysts and recommends a
retired cryptanalyst who might be helpful.

	A tougher problem arises when the observer doesn't get the
sequence of x-coordinates but only 1 or 0 according to whether the
ball is visible or invisible.

John Kelley accepted (on Nov 24, 1980) the following cS206 problem

	Write a LISP program to implement the following functions:

(a t) gives 0 if the ball is invisible at time t
	    1 if the ball is moving to the right at t
	    2 if the ball is moving to the left at t

(b) initializes the ball

(c) gets a new configuration at random

(d t) gives the x-component of the velocity at time t

(save x) stores the configuration as the LISP variable x

(restore x) loads the configuration from the LISP variable x

	Here is one way of implementing the function that finds position
and velocity as a function of time.  It is necessary to go forward or
backward from a time when these things are known.

	1. Each edge of a rectangle is represented by a pair of functions
x = x0 + u0*s, y = y0 + v0*s together with limits s0 and s1.

	2. The position of the ball is represented by x = x0' + u0'*(t - t0),
y = y0' + v0'*(t - t0) from the time t0 until the ball hits something.

	3. Compute the interstection of the trajectory with each edge and
eliminated those edges for which the values of s are out of range.

	4. Choose that intersection with the least value of t > t0.

	5. Reflect at that point and continue the process.

Linear programming techniques can probably give something more sophisticated,
but it won't be needed if we keep down the number of rectangles.

	Whether the ball is visible at a given time is computed similarly,
but for that it is worthwhile to have the back edges represented by giving
y as a function of x and scanning over the ranges of x to determine the
function to compare y with.

	Since it might be interesting to get someone to try to figure out
the rule of the sequence, I suggest you don't talk about the problem except
with people who agree not to talk.

Note of 1985 Dec 27

	The problem has been given the following standard form.  The
observer sees only a sequence of 0s and 1s according to whether the
ball is visible or not.  It is invisible when it goes under a roof.

This is SEQUEN[F80,JMC].

Note of 1987 Oct 30

∂30-Oct-87  0100	LAWS@KL.SRI.Com 	AIList V5 #253 - LISP, NIL, Msc. 
Date: 29 Oct 87 04:22:27 GMT
From: mind!eliot@princeton.edu  (Eliot Handleman)
Subject: Prediction-producing Algorithms

I am looking for any work done on predictive algorithms - by which I
mean something that, given some input, is able to make a reasonable stab
at a plausible continuation. I am decidedly not interested in things which
compute transition probablities. Something which is able to generated
some pattern of inference is more up my alley.
For example, if I fed the pattern a a b a a b a into this thing, I would
expect to get back a b as the most reasonable thing to expect.
Any pointers to articles, dissertations, texts, programs etc would be
extremely helpful. Please ship your replies to me directly, and many
thanks in advance.